//给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改
// 数组以供接下来的操作使用。 
//
// 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,4,2,3], x = 5
//输出：2
//解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [5,6,7,8,9], x = 4
//输出：-1
// 
//
// 示例 3： 
//
// 
//输入：nums = [3,2,20,1,1,3], x = 10
//输出：5
//解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// 1 <= nums[i] <= 104 
// 1 <= x <= 109 
// 
// Related Topics 数组 哈希表 双指针 二分查找 前缀和 
// 👍 65 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minOperations(int[] nums, int x) {
        int ret = -1;
//        System.out.println("nums:"+Arrays.toString(nums));
        //初始化两个前缀和数组
        int[] preSumLeft = new int[nums.length+1];
        int[] preSumRight = new int[nums.length+1];

        //弄一个虚头，以便能够覆盖所有场景，方便后续写循环代码，代表0个元素的前缀和
        preSumLeft[0] = 0;
        preSumRight[0] = 0;

        for(int i=0; i<nums.length; i++){
//            System.out.println("i\t"+i);
            preSumLeft[i+1] = preSumLeft[i] + nums[i];
            preSumRight[i+1] = preSumRight[i] + nums[nums.length -1 - i];
        }
//        System.out.println("preSumLeft\t"+Arrays.toString(preSumLeft));
//        System.out.println("preSumRight\t"+Arrays.toString(preSumRight));

        //遍历左前缀和数组，计算还剩多少，再从右前缀和数组中查找能否找到剩的
        for (int i=0; i< preSumLeft.length; i++){
            int left = preSumLeft[i];
//            if(left == x){
//                if(ret == -1) ret = i;
//                else ret = Math.min(ret,i);
//            }

            int remain = x - left;
            //0,1,2,3,4,5,6,7
            //7,6,5,4,3,2,1,0
            int to = preSumLeft.length-i-1;
            int rightIndex = binarySearch(preSumRight,to,remain);
//            System.out.println("index:"+i+", left:"+left+", remain:"+remain+", to:"+to+", rightIndex:"+rightIndex);
            if(rightIndex == -1) continue;
            if(ret == -1 || ret >= i + rightIndex){
                ret = i + rightIndex;
            }
        }
        return ret;
    }
    public int binarySearch(int[] nums, int to, int target){
        int head = 0, tail = to, mid;
        while(tail - head > 3){
            mid = head + ((tail - head) >> 1);
            if( nums[mid] == target ) return mid;
            else if ( nums[mid] > target ) tail = mid -1;
            else head = mid + 1;
        }
        for(int i = head; i<=tail; i++){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
